﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.StateSpaces;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using Sets = Algoritmia.DataStructures.Sets;

namespace Algoritmia.Schemes
{
    public class BacktrackingEnumerator<TState,TDecision,TSolution>
    {
        #region Factory Methods

        private readonly Func<Lists.IList<TDecision>> _createList;
        private readonly Func<IForwardStateSpace<TState, TDecision>, Sets.ISet<TState>> _createSet;
        private readonly Func<IForwardStateSpace<TState, TDecision>, TState, Lists.IList<TDecision>, TState, TSolution> _createSolution;

        #endregion

        #region Temporary members for Enumerate method

        private TState _initial;
        private Lists.IList<TDecision> _decisions;
        private Sets.ISet<TState> _seen;
        private IForwardStateSpace<TState, TDecision> _space;
        private IReversibleForwardStateSpace<TState, TDecision> _reversibleSpace;

        #endregion

        public BacktrackingEnumerator(
            Func<IForwardStateSpace<TState,TDecision>,TState,Lists.IList<TDecision>,TState,TSolution> createSolution,
            Func<IForwardStateSpace<TState,TDecision>,Sets.ISet<TState>> createSet = null,
            Func<Lists.IList<TDecision>> createList = null
            )
        {
            _createSolution = createSolution;
            _createSet = createSet ?? (stSpace => new Sets.DummySet<TState>());
            _createList = createList ?? (() => AlgoritmiaFactory.Lists<TDecision>.Default);

        }

        public IEnumerable<TSolution> Enumerate(IForwardStateSpace<TState,TDecision> space)
        {
            _space = space;
            _reversibleSpace = space as IReversibleForwardStateSpace<TState, TDecision>;
            _decisions = _createList();
            _seen = _createSet(space);
            foreach(var initial in space.InitialStates)
            {
                _initial = initial;
                foreach(var result in Backtracking(initial))
                {
                    yield return result;
                }
            }
        }

        public TSolution First(IForwardStateSpace<TState,TDecision> space)
        {
            TSolution solution;

            try
            {
                solution = Enumerate(space).First();
            }
            catch (InvalidOperationException)
            {
                throw new InvalidOperationException("No solution found");
            }
            return solution;
        }

        private IEnumerable<TSolution> Backtracking(TState state)
        {
            if (_space.IsFinal(state))
                yield return _createSolution(_space, _initial, _decisions, state);
            _seen.Add(state);
            foreach(var decision in _space.Decisions(state))
            {
                _decisions.Add(decision);
                var successor = _space.Decide(state, decision);
                if (!_seen.Contains(successor))
                {
                    foreach (var result in Backtracking(successor))
                        yield return result;
                }
                if (_reversibleSpace != null)
                {
                    state = _reversibleSpace.Undo(successor, decision);
                }
                _decisions.RemoveAt(_decisions.Count-1);
            }   
         }
    }
}
